package ch02Sort;

import com.sun.javafx.tk.TKPulseListener;

//快速排序
/*
快速排序将数组排序的方式是当两个子数组都有序时，整个数组自然就有序了
 */
public class Quick extends Sort {

    public static void sort(Comparable[] a) {
        int n = a.length;
        sort(a,0,n-1);
    }

    public static void sort(Comparable[] a, int lo, int hi) {
        if(lo>=hi) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    public static int partition(Comparable[] a, int lo, int hi) {
        //切分点
        Comparable v = a[lo];
        int i = lo;
        //为了--j与++i对应
        int j = hi + 1;
        while (true) {
            //遇到比切分点大的i元素就break
            while (less(a[++i], v)) {
                if (i >= hi)
                    break;
            }
            //遇到比切分点小的j元素就break
            while (less(v, a[--j])) {
                if (j <= lo)
                    break;

            }
            //必须写在exch之前，否则i,j错误交换又会导致lo,j错误交换
            if(i>=j)
                break;
            exch(a,i,j);

        }
        //必须交换j，因为当i>=j break之后j在i的位置或者i的左边，
        // 左边的元素比切分点小可以和切分点交换
        exch(a,lo,j);
        return j;

    }
    public static void swap(int[] a){
        int t = a[0];
        a[0] = a[1];
        a[1] = t;
    }

    public static void main(String[] args) {

        sort(Sort.a);
        System.out.print("现数组：");
        show(Sort.a);
        System.out.print("isSorted？");
        System.out.println(isSorted(Sort.a));
        Integer[] a = new Integer[]{46, 79, 56, 38, 40, 84};
        sort(a);
        show(a);



    }
}
